The present invention relates to a method and apparatus for securely authenticating a device or signing digital contents using a public-key cryptosystem, with an extremely limited computational power or no computation unit at all.
Authentication plays a crucial role for fighting against piracy, unauthorized copying or counterfeiting. For example, it has applications in secure passports, which embed a wireless communication-enabled chip for authenticating the holder of the passport, or for anti-counterfeiting purposes, where authentication chips certify the origin of products. In addition, copyrighted digital media include authentication tokens known as DRM (digital right managements) in order to prevent unauthorized actions such as piracy. As a consequence, their support (CD, DVD, memory cards or other equivalent memory supports) often includes authentication mechanisms. Finally, authentication can be useful to prevent competitors from reverse-engineering a product, and mass-produce it at a cheaper price. For instance, printer cartridges could be equipped with an authentication chip in order to prevent the usage of refill kits or rogue cartridges manufactured by competitors.
Authentication consists of a protocol where a prover exhibits a proof of his identity to a verifier. Usually, the verifier sends a challenge which can be solved by the prover only. When the challenge relies on symmetric key cryptography, the prover and the verifier have to share a common secret key, whereas in the case of public-key cryptography, only the prover owns the secret key, and any verifier can check the solution of the challenge provided by the prover.
It is expected that RFID chips will be widely used for authentication means in a near future; however, the current technology only allows the storage of a tag, that is, a unique ID number, which is broadcasted in clear using a radio transmission. Therefore, anyone listening to the transmission frequency can get the knowledge of the tag and later clone it. Using a protocol based on symmetric-key cryptography is a better solution, since the transmission between the prover and the verifier can be encrypted. However, ID fraud can occur when the verifier is dishonest or compromised, since the secret key is shared by the prover and the verifier. In addition, in most scenarios, one verifier must be able to authenticate many provers; if only one verifier is compromised, all secret keys are revealed and all of the provers will be compromised as well. Besides, in the framework of an anti-counterfeiting system, the verifier might have to be able to authenticate a whole line of products, and not individual products. When the line of products consists of several million of units, storing all keys is prohibitive. In this case, instead of having one secret key per unit, at first sight, having one key for the whole line appears to be a better idea. Unfortunately, compromising only one unit also means compromising the whole line of products.
Alternatively, public-key cryptosystems, and in particular digital signatures, can be used for authentication purposes. The verifier sends a random message to the prover, who signs the message using his secret key. Then, the verifier can check the prover's identity by verifying the signature using the prover's public key only, and not the secret key. An authentication system based on public-key cryptography has the advantage that the verifier cannot impersonate the prover, since he does not know the prover's secret key. In addition, using a public-key infrastructure allows an easy authentication of a line of product: the prover digitally signs the challenge, and provides his public key and a certificate for his public key, which includes a digital signature of the prover's public key, signed by a certificate authority. Then the verifier can verify both signatures in order to confirm the identity of the prover. This approach does not only eliminate the storage requirements of the verifier, which has to store the verification means for the certificate (for example a single public key for a whole product line, where the public key is obtained from the manufacturing company), and not that of individual units, but also includes an easy revocation mechanism. When a prover's secret key is known to be compromised, his public key can be sent in a black list to all verifiers.
Patent literature 1: Liam D. Comerford, Vernon E. Shrauger: “Write-once-read-once batteryless authentication token”, US5032708 (IBM), 1991.
Nonpatent literature 2: Amos Fiat, Adi Shamir: How to Prove Yourself: Practical Solutions to Identification and Signature Problems. CRYPTO 1986: 186-194.
Nonpatent literature 3: Ralph C. Merkle: A Certified Digital Signature. CRYPTO 1989: 218-238.